﻿using System;
using System.Collections.Generic;
using System.Threading;

namespace RLProject1.Model.AMEEWorld
{
    /// <summary>
    /// Spezialisierte Kollektion zum Speichern von Zustand-IDs. Threadsafe.<para>
    /// Vorne hinzufügen, hinten entfernen oder abschneiden in O(1).</para><para>
    /// Enumerates vom neuesten zum ältesten Element (wie beim Stack).</para>
    /// </summary>
    class BesuchteZustaende : IList<int>
    {
        /// <summary>
        /// Die Elemente. Neueste stehen am Ende.
        /// </summary>
        int[] elemente;
        /// <summary> 43. Standard Startlänge des elemente-Arrays.</summary>
        static int _standardStartLaenge = 43;
        /// <summary>Initiale Kapazität.</summary>
        int startLaenge;
        /// <summary>90 (Prozent)</summary>
        static int _obereFuellGrenze = 90;
        /// <summary>10 (Prozent)</summary>
        static int _untereFuellGrenze = 10;
        /// <summary>Index des ersten=ältesten Elements.</summary>
        int first = 0;
        /// <summary>Index des letzten=neuesten Elements</summary>
        int last = 0;
        /// <summary>Anzahl gespeicherter Elemente.</summary>
        int count = 0;

        private ReaderWriterLockSlim rwLock = new ReaderWriterLockSlim();

        #region Konstruktoren
        /// <summary>
        /// Initializes a new instance of the <see cref="BesuchteZustaende"/> class.
        /// </summary>
        public BesuchteZustaende() : this(_standardStartLaenge){
        }
        /// <summary>
        /// Initializes a new instance of the <see cref="BesuchteZustaende"/> class.
        /// </summary>
        /// <param name="capacity">The initial capacity.</param>
        /// <exception cref="System.ArgumentOutOfRangeException">capacity must be at least 1.</exception>
        public BesuchteZustaende(int capacity) {
            if (capacity < 1)
                throw new ArgumentOutOfRangeException("capacity","Must be at least 1.");
            elemente = new int[capacity];
            startLaenge = capacity;
        }
        #endregion


        #region IEnumerable

        /// <summary>
        /// Gibt den Enumerator, der diese Kollektion vom neusten zum ältesten Element durchläuft.<para>
        /// (ähnlich einem Stack).</para>
        /// </summary>
        /// <returns>the enumerator.</returns>
        public IEnumerator<int> GetEnumerator() {
            int[] elems = new int[count]; //! nur 99,9% Threadsafe !
            this.CopyTo(elems, 0);
            return new BZEnumerator(elems);
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }
        #endregion


        #region IList

        /// <summary>
        /// Determines the index of a specific item in the BesuchteZustaende.<para>
        /// Dauer: O(N)</para><para>
        /// Das zuletzt mit Add hinzugefügte Element hat den Index 0.</para>
        /// </summary>
        /// <param name="item">The number to locate</param>
        /// <returns>The index of item if found in the list; otherwise, -1.</returns>
        public int IndexOf(int item) {
            int retVal = -1;
            rwLock.EnterReadLock();
            for (int i = 0; i < count; i++) { // optimierungsfähig
                if (item == elemente[getArrayIndex(i)])
                    retVal = i;
            }
            rwLock.ExitReadLock();
            return retVal;
        }

        /// <summary>
        /// Sets at given index the specified item.<para>
        /// Same as besuchteZustaende[index] = item.</para><para>
        /// Dauer: O(1)
        /// </para>
        /// </summary>
        /// <param name="index">The index.</param>
        /// <param name="item">The item.</param>
        /// <exception cref="System.ArgumentOutOfRangeException">
        /// index negativ or greater Count-1
        /// </exception>
        public void Insert(int index, int item) {
            this[index] = item;
        }

        /// <summary>
        /// Entfernt das Element am spezifizierten Index und<para>
        /// verschiebt hintere um eine Stelle nach vorne.</para><para>
        /// Dauer: O(N)</para>
        /// </summary>
        /// <param name="index">Index</param>
        /// <remarks>Existiert der Index nicht, passiert nichts.</remarks>
        public void RemoveAt(int index) {
            if (index < 0)
                return;
            rwLock.EnterWriteLock();
            try {
                if (count == 0)
                    return;
                if (index > count - 1)
                    return;

                int idx = getArrayIndex(index);
                if (idx == first) { // entfernen vom Anfang
                    first = (first + 1) % elemente.Length;
                    count--;
                }
                else if (idx == last) { // entfernen vom Ende
                    last = last == 0 ? elemente.Length : last - 1;
                    count--;
                }
                else {
                    // Entfernen innerhalb durch linksschieben der oberen Elemente
                    for (int i = idx; i != (last + 1) % elemente.Length; i = (i++) % elemente.Length) {
                        elemente[i] = elemente[(i + 1) % elemente.Length];
                    }
                    last = (last == 0) ? (elemente.Length - 1) : (last - 1);
                    count--;
                }
            }
            finally {
                rwLock.ExitWriteLock();
            }
            checkLowerThreshold();
        }

        /// <summary>
        /// Gets or sets the <see cref="System.Int32"/> at the specified index.<para>
        /// Dauer: O(1)</para>
        /// </summary>
        /// <value>
        /// The <see cref="System.Int32"/> value.
        /// </value>
        /// <param name="index">The index.</param>
        /// <returns></returns>
        /// <exception cref="System.ArgumentOutOfRangeException">
        /// index negativ or greater Count-1
        /// </exception>
        public int this[int index] {
            get {
                if (index < 0 || index >= count)
                    throw new ArgumentOutOfRangeException("index");
                rwLock.EnterReadLock();
                int retVal = elemente[this.getArrayIndex(index)];
                rwLock.ExitReadLock();
                return retVal;
            }
            set {
                if (index < 0 || index >= count)
                    throw new ArgumentOutOfRangeException("index");
                rwLock.EnterWriteLock();
                elemente[this.getArrayIndex(index)] = value;
                rwLock.ExitWriteLock();
            }
        }

        /// <summary>
        /// Fügt vorne an.<para>
        /// Dauer: O(1) im Normalfall.</para>
        /// </summary>
        /// <param name="item">The item.</param>
        public void Add(int item) {
            rwLock.EnterWriteLock();
            try {
                if (count == 0)
                    elemente[last] = item;
                else {
                    int index = (last + 1) % elemente.Length;
                    elemente[index] = item;
                    last = index;
                }
                count++;
            }
            finally {
                rwLock.ExitWriteLock();
            }
            checkUpperThreshold();
        }

        /// <summary>
        /// Removes all items from the <see cref="BesuchteZustaende"/>.<para>
        /// Dauer: O(1). Kapazität bleibt unverändert.</para>
        /// </summary>
        public void Clear() {
            rwLock.EnterWriteLock();
            first = 0;
            last = 0;
            count = 0;
            rwLock.ExitWriteLock();
        }

        /// <summary>
        /// Determines whether the BesuchteZustaende contains a specific value.<para>
        /// Dauer: O(n)</para>
        /// </summary>
        /// <param name="item">The item.</param>
        /// <returns>
        ///   <c>true</c> if contains the specified item; otherwise, <c>false</c>.
        /// </returns>
        public bool Contains(int item) {
            bool retVal = false;
            rwLock.EnterReadLock();
            for (int i=0; i < count; i++) {
                    int idx = (first + i) % elemente.Length;
                    if (elemente[idx] == item)
                        retVal = true;
                }
            rwLock.ExitReadLock();
            return retVal;
        }

        /// <summary>
        /// Copies the elements of the BesuchteZustaende to an <see cref="System.Array" />, starting at a particular Array index
        /// </summary>
        /// <param name="array">The one-dimensional Array that is the destination of the elements copied from <see cref="BesuchteZustaende" />. The Array must have zero-based indexing.</param>
        /// <param name="arrayIndex">The zero-based index in <c>array</c> at which copying begins.</param>
        /// <exception cref="System.ArgumentNullException">array is null.</exception>
        /// <exception cref="System.ArgumentOutOfRangeException">arrayIndex is less than 0.</exception>
        /// <exception cref="System.ArgumentException">The number of elements in the source BesuchteZustaende is greater than the available space from arrayIndex to the end of the destination array.</exception>
        public void CopyTo(int[] array, int arrayIndex) {
            if (array == null)
                throw new ArgumentNullException("array", "array is null.");
            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException("arrayIndex", "arrayIndex is less than 0.");
            if (this.count > (array.Length - arrayIndex))
                throw new ArgumentException("The number of elements in the source BesuchteZustaende is greater than the available space from arrayIndex to the end of the destination array.");
            rwLock.EnterReadLock();
            try {
                // Kopieren der Elemente (ggf. 0)
                int idx2 = 0;
                for (int i = last; idx2 < count; i--) {
                    if (i < 0)
                        i = elemente.Length - 1;
                    array[arrayIndex + idx2] = elemente[i];
                    idx2++;
                }
            }
            finally {
                rwLock.ExitReadLock();
            }
        }

        /// <summary>
        /// Gets the number of elements contained in the BesuchteZustaende.
        /// </summary>
        public int Count {
            get { return count; }
        }

        /// <summary>
        /// False.
        /// </summary>
        public bool IsReadOnly {
            get { return false; }
        }

        /// <summary>
        /// Removes the last occurrence of a specific object from the <see cref="BesuchteZustaende"/>.<para>
        /// Dauer: O(n)</para>
        /// </summary>
        /// <param name="item">The item.</param>
        /// <returns>
        /// <c>true</c> if item was successfully removed from the BesuchteZustaende; otherwise, <c>false</c>. This method also returns false if item is not found in the original BesuchteZustaende.
        /// </returns>
        public bool Remove(int item) {
            bool retVal = false;
            rwLock.EnterUpgradeableReadLock();
            try {
                for (int i = 0; i < count; i++) {
                    int idx = (first + i) % elemente.Length;
                    if (elemente[idx] == item) {
                        try {
                            rwLock.EnterWriteLock();
                            this.RemoveAt(i);
                            retVal = true;
                        }
                        finally {
                            rwLock.ExitWriteLock();
                        }
                        break;
                    }
                }
            }
            finally {
                rwLock.ExitUpgradeableReadLock();
            }
            return retVal;
        }

        #endregion


        #region private Helpers

        /// <summary>
        /// Checks the upper threshold.<para>
        /// Bei 90% Füllstand wird in ein 1,5-fach längeres Array umkopiert</para>
        /// </summary>
        void checkUpperThreshold() {
            int[] neu = null;
            bool isToCopy = false;
            rwLock.EnterReadLock();
            try {
                int fuellStand = count * 100 / elemente.Length;
                isToCopy = fuellStand >= _obereFuellGrenze;
                if (isToCopy) {
                    int length = elemente.Length + (elemente.Length >> 1);
                    neu = new int[length];
                    for (int i = 0; i < count; i++) {
                        int idx = (first + i) % elemente.Length;
                        neu[i] = elemente[idx];
                    }
                }
            }
            finally {
                rwLock.ExitReadLock();
            }
            if (isToCopy) {
                rwLock.EnterWriteLock();
                first = 0;
                last = count - 1;
                elemente = neu;
                rwLock.ExitWriteLock();
            }
        }

        /// <summary>
        /// Checks the lower threshold.<para>
        /// Bei 90% Füllstand wird in ein 1,5-fach längeres Array umkopiert</para>
        /// </summary>
        void checkLowerThreshold() {
            int[] neu = null;
            bool isToCopy = false;
            rwLock.EnterReadLock();
            try {
                int fuellStand = count * 100 / elemente.Length;
                isToCopy = elemente.Length > this.startLaenge && fuellStand < _untereFuellGrenze;
                if (isToCopy) {
                    int length = (int)(elemente.Length / 1.5);
                    neu = new int[length];
                    for (int i = 0; i < count; i++) {
                        int idx = (first + i) % elemente.Length;
                        neu[i] = elemente[idx];
                    }
                }
            }
            finally {
                rwLock.ExitReadLock();
            }
            if (isToCopy) {
                rwLock.EnterWriteLock();
                first = 0;
                last = count - 1;
                elemente = neu;
                rwLock.ExitWriteLock();
            }
        }

        /// <summary>
        /// Gibt den Array-Index zum gegebenen abstrakten Index.<para>
        /// (0->last und count-1->first)</para><para>
        /// Ohne Lock !</para>
        /// </summary>
        /// <param name="publicIndex">Öffentlicher, abstrahierter Index</param>
        /// <returns>Array-Index</returns>
        int getArrayIndex(int publicIndex) {
            return (first + (count - 1) - publicIndex) % elemente.Length;
        }

        #endregion


        #region Public Spezialmethoden

        /// <summary>
        /// Entfernt alle Elemente ab dem spezifizierten Index inklusive.<para>
        /// Dauer: O(1) im Normalfall.</para>
        /// </summary>
        /// <param name="index">Der index, ab dem inklusive entfernt wird.</param>
        public void Truncate(int index) {
            if (index < 0)
                return;
            rwLock.EnterWriteLock();
            try {
                if (index > count - 1)
                    return;

                if (index == 0) {// alle Entfernen
                    last = 0;
                    first = last;
                    count = 0;
                    return;
                }
                // truncate durch verschieben des ältesten=first Zeigers
                int idx = getArrayIndex(index);
                first = (idx + 1) % elemente.Length;
                count = index;
            }
            finally {
                rwLock.ExitWriteLock();
            }
            checkLowerThreshold();
        }

        /// <summary>
        /// Entfernt das letzte (älteste) Element.
        /// </summary>
        public void RemoveLast() {
            if (count == 0)
                return;

            first = (first + 1) % elemente.Length;
            count--;
            if (count == 0)
                last = first;
        }

        #endregion




        /// <summary>
        /// Innere Enumerator-Klasse für BesuchteZustaende.
        /// </summary>
        private class BZEnumerator : IEnumerator<int>
        {
            int[] elements;
            int currIdx;
            private bool disposed = false;


            public BZEnumerator(int[] elements) {
                if (elements == null)
                    this.elements = new int[0];
                this.elements = elements;
                currIdx = -1;
            }

            #region IEnumerator
            /// <summary>
            /// Gets the current element.<para>
            /// Es muss mindestens einmal MoveNext aufgerufen und mit true beantwortet werden.</para>
            /// </summary>
            /// <exception cref="System.InvalidOperationException">
            /// Es muss mindestens einmal MoveNext aufgerufen bzw. mit true beantwortet werden.</exception>
            public int Current {
                get {
                    try {
                        return elements[currIdx];
                    }
                    catch (IndexOutOfRangeException) {
                        throw new InvalidOperationException();
                    }
                }
            }

            public void Dispose() {
                Dispose(true);
                GC.SuppressFinalize(this);
            }

            object System.Collections.IEnumerator.Current {
                get { return Current; }
            }

            public bool MoveNext() {
                currIdx++;
                return currIdx < elements.Length;
            }

            public void Reset() {
                currIdx = -1;
            }
            #endregion

            protected virtual void Dispose(bool disposing) {
                if (!disposed) {
                    if (disposing) {
                        // Free other state (managed objects).
                        elements = null;
                    }
                    // Free your own state (unmanaged objects).
                    // Set large fields to null.
                    disposed = true;
                }
            }

            // Use C# destructor syntax for finalization code.
            ~BZEnumerator() {
                // Simply call Dispose(false).
                Dispose(false);
            }

        }
    }


}
